<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="bSS6G" id="bSS6G"><span data-lake-id="ua7b00087" id="ua7b00087">典型回答</span></h1>
  <p data-lake-id="u17b760ca" id="u17b760ca"><span data-lake-id="u5ca9c27e" id="u5ca9c27e">哈希算法大家都不陌生，经常被用在负载均衡、分库分表等场景中，比如说我们在做分库分表的时候，最开始我们根据业务预估，把数据库分成了128张表，这时候要插入或者查询一条记录的时候，我们就会先把分表键，如buyer_id进行hash运算，然后再对128取模，得到0-127之间的数字，这样就可以唯一定位到一个分表。</span></p>
  <p data-lake-id="ucf39155b" id="ucf39155b"><br></p>
  <p data-lake-id="u2b5bd8fe" id="u2b5bd8fe"><span data-lake-id="ufa299006" id="ufa299006">但是随着业务得突飞猛进，128张表，已经不够用了，这时候就需要重新分表，比如增加一张新的表。这时候如果采用hash或者取模的方式，就会导致128+1张表的数据都需要重新分配，成本巨高。</span></p>
  <p data-lake-id="ua2b46465" id="ua2b46465"><br></p>
  <p data-lake-id="u4bdf1a8f" id="u4bdf1a8f"><span data-lake-id="ub510128e" id="ub510128e">而一致性hash算法， 就能有效的解决这种分布式系统中增加或者删除节点时的失效问题。</span></p>
  <p data-lake-id="u269072f8" id="u269072f8"><span data-lake-id="u22870493" id="u22870493">​</span><br></p>
  <p data-lake-id="u4d79ac6f" id="u4d79ac6f"><strong><span data-lake-id="u6d6fcb8a" id="u6d6fcb8a">一致性哈希（Consistent Hashing）是一种用于分布式系统中数据分片和负载均衡的算法。它的目标是在节点的动态增加或删除时，尽可能地减少数据迁移和重新分布的成本。</span></strong></p>
  <p data-lake-id="u8f443b5b" id="u8f443b5b"><br></p>
  <p data-lake-id="u1a7b2093" id="u1a7b2093"><span data-lake-id="ue1c0ab11" id="ue1c0ab11">实现一致性哈希算法首先需要构造一个哈希环，然后把他划分为固定数量的虚拟节点，如2^32。那么他的节点编号就是 0-2^32-1：</span></p>
  <p data-lake-id="ua48ab6d3" id="ua48ab6d3"><span data-lake-id="u58d09427" id="u58d09427">​</span><br></p>
  <p data-lake-id="u713c4f52" id="u713c4f52"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1690098084933-99c0b0f3-d884-4085-8185-ff223e34396f.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_22%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u4c4e452f" id="u4c4e452f"><span data-lake-id="u4d61584b" id="u4d61584b">​</span><br></p>
  <p data-lake-id="ub83e68ae" id="ub83e68ae"><span data-lake-id="u343d731a" id="u343d731a">接下来， 我们把128张表作为节点映射到这些虚拟节点上，每个节点在哈希空间上都有一个对应的虚拟节点：</span></p>
  <p data-lake-id="ue76944ec" id="ue76944ec"><span data-lake-id="ua5a9fb6c" id="ua5a9fb6c">​</span><br></p>
  <p data-lake-id="u81874889" id="u81874889"><span data-lake-id="u1df8d219" id="u1df8d219">hash(table_0000)%2^32、hash(table_0001)%2^32、hash(table_0002)%2^32 .... hash(table_0127)%2^32</span></p>
  <p data-lake-id="u7d9a4217" id="u7d9a4217"><span data-lake-id="ue2f13e7b" id="ue2f13e7b">​</span><br></p>
  <p data-lake-id="udeca446b" id="udeca446b"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1690098355931-a7fbefda-fcae-48f9-ada8-6311f90df85d.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_26%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="udc8ca097" id="udc8ca097"><br></p>
  <p data-lake-id="u00d7c259" id="u00d7c259"><span data-lake-id="u8842b7f8" id="u8842b7f8">再把这些表做好hash映射之后，我们就需要存储数据了，现在我们要把一些需要分表的数据也根据同样的算法进行hash，并且也将其映射哈希环上。</span></p>
  <p data-lake-id="u6f3771df" id="u6f3771df"><span data-lake-id="udc7339f0" id="udc7339f0">​</span><br></p>
  <p data-lake-id="u88068f47" id="u88068f47"><span data-lake-id="u9755a0ae" id="u9755a0ae">hash(buyer_id)%2^32：</span></p>
  <p data-lake-id="ube1713a8" id="ube1713a8"><span data-lake-id="uf8978c9b" id="uf8978c9b">hash(12321)%2^32、hash(34432)%2^32、hash(54543)%2^32 .... hash(767676)%2^32</span></p>
  <p data-lake-id="u5dc09901" id="u5dc09901"><span data-lake-id="ub85e7eab" id="ub85e7eab">​</span><br></p>
  <p data-lake-id="ua7d2c378" id="ua7d2c378"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1690099178821-cd8ad4e5-9ca9-4904-8665-f6e9c608acb6.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_26%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u234eef5b" id="u234eef5b"><span data-lake-id="ue096f12a" id="ue096f12a">​</span><br></p>
  <p data-lake-id="uc4bd5003" id="uc4bd5003"><span data-lake-id="u6e876676" id="u6e876676">这样，这个hash环上的虚拟节点就包含两部分数据的映射了，一部分是存储数据的分表的映射，一部分是真实要存储的数据的映射。</span></p>
  <p data-lake-id="u8b9364e1" id="u8b9364e1"><span data-lake-id="ubcbcd2b6" id="ubcbcd2b6">​</span><br></p>
  <p data-lake-id="uf6d20bd1" id="uf6d20bd1"><span data-lake-id="uf82e0787" id="uf82e0787">那么， 我们最终还是要把这些数据存储到数据库分表中，那么做好哈希之后，这些数据又要保存在哪个数据库表节点中呢？</span></p>
  <p data-lake-id="ueef3f203" id="ueef3f203"><span data-lake-id="u325e85e7" id="u325e85e7">​</span><br></p>
  <p data-lake-id="ud0d0c5a5" id="ud0d0c5a5"><span data-lake-id="u4ac6d721" id="u4ac6d721">其实很简单，只需要按照数据的位置，沿着顺时针方向查找，找到的第一个分表节点就是数据应该存放的节点：</span></p>
  <p data-lake-id="u06950be5" id="u06950be5"><span data-lake-id="uad8ea632" id="uad8ea632">​</span><br></p>
  <p data-lake-id="uac780acb" id="uac780acb"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1690099212024-9ac0a5b0-974b-4307-b78a-f7545257c0c5.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_24%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="uba452fa2" id="uba452fa2"><span data-lake-id="ueb851725" id="ueb851725">​</span><br></p>
  <p data-lake-id="u827383a4" id="u827383a4"><span data-lake-id="u82e72c06" id="u82e72c06">因为要存储的数据，以及存储这些数据的数据库分表，hash后的值都是固定的，所以在数据库数量不变的情况下，下次想要查询数据的时候，只需要按照同样的算法计算一次就能找到对应的分表了。</span></p>
  <p data-lake-id="u581c58f3" id="u581c58f3"><span data-lake-id="uaee19003" id="uaee19003">​</span><br></p>
  <p data-lake-id="u605b3dbd" id="u605b3dbd"><span data-lake-id="uf0a3b277" id="uf0a3b277">以上，就是一致性hash算法的原理，那么，再回到我们开头的问题，如果我要增加一个分表怎么办呢？</span></p>
  <p data-lake-id="u068e0b19" id="u068e0b19"><span data-lake-id="u36c53a3f" id="u36c53a3f">​</span><br></p>
  <p data-lake-id="u027a0097" id="u027a0097"><span data-lake-id="ud8d57a89" id="ud8d57a89">我们首先要将新增加的表通过一致性hash算法映射到哈希环的虚拟节点中：</span></p>
  <p data-lake-id="uea7d8b78" id="uea7d8b78"><span data-lake-id="u2dbfc20c" id="u2dbfc20c">​</span><br></p>
  <p data-lake-id="ub7410ab2" id="ub7410ab2"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1690099259966-9dbb75de-fa74-4365-86bb-7bf19fead4b8.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_26%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u5fdbfc55" id="u5fdbfc55"><span data-lake-id="udbf655d9" id="udbf655d9">​</span><br></p>
  <p data-lake-id="u840c7134" id="u840c7134"><span data-lake-id="ud9d7690c" id="ud9d7690c">这样，会有一部分数据，因为节点数量发生变化，那么他顺时针遇到的第一个分表可能就变了。</span></p>
  <p data-lake-id="u33959b27" id="u33959b27"><span data-lake-id="uffdec550" id="uffdec550">​</span><br></p>
  <p data-lake-id="u398a34ba" id="u398a34ba"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1690099325961-ac1ac0eb-4d84-49da-a94e-517c44cbb189.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_26%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u63cd76b9" id="u63cd76b9"><br></p>
  <p data-lake-id="uacbd1883" id="uacbd1883"><span data-lake-id="u6b1a9a59" id="u6b1a9a59">相比于普通hash算法，在增加服务器之后，影响的范围非常小，只影响到一部分数据，其他的数据是不需要调整的。</span></p>
  <p data-lake-id="u1ac8eb4b" id="u1ac8eb4b"><span data-lake-id="uf6570488" id="uf6570488">​</span><br></p>
  <p data-lake-id="u3a3895c6" id="u3a3895c6"><span data-lake-id="u6613e023" id="u6613e023">​</span><br></p>
  <p data-lake-id="uf52be19d" id="uf52be19d"><span data-lake-id="uc5a752aa" id="uc5a752aa">所以，</span><strong><span data-lake-id="udcbd5c98" id="udcbd5c98">在总结一下。一致性哈希算法将整个哈希空间视为一个环状结构，将节点和数据都映射到这个环上。每个节点通过计算一个哈希值，将节点映射到环上的一个位置。而数据也通过计算一个哈希值，将数据映射到环上的一个位置。</span></strong></p>
  <p data-lake-id="u06a7a756" id="u06a7a756"><strong><span data-lake-id="ua6313765" id="ua6313765">​</span></strong><br></p>
  <p data-lake-id="ua26811d0" id="ua26811d0"><strong><span data-lake-id="u3c60e8a7" id="u3c60e8a7">当有新的数据需要存储时，首先计算数据的哈希值，然后顺时针或逆时针在环上找到最近的节点，将数据存储在这个节点上。当需要查找数据时，同样计算数据的哈希值，然后顺时针或逆时针在环上找到最近的节点，从该节点获取数据。</span></strong></p>
  <p data-lake-id="u1f2ef1e2" id="u1f2ef1e2"><span data-lake-id="u2657a4b5" id="u2657a4b5">​</span><br></p>
  <p data-lake-id="u3caa7c13" id="u3caa7c13"><span data-lake-id="ud12dba40" id="ud12dba40">优点：</span></p>
  <p data-lake-id="u1404b8cb" id="u1404b8cb"><span data-lake-id="ude1707af" id="ude1707af">​</span><br></p>
  <ol list="u7e80ed32">
   <li fid="u03a961f5" data-lake-id="uf1b922f7" id="uf1b922f7"><strong><span data-lake-id="u5a73f21e" id="u5a73f21e">数据均衡</span></strong><span data-lake-id="u379e7a1d" id="u379e7a1d">：在增加或删除节点时，一致性哈希算法只会影响到少量的数据迁移，保持了数据的均衡性。</span></li>
   <li fid="u03a961f5" data-lake-id="uccd39ca1" id="uccd39ca1"><strong><span data-lake-id="u6356b4c0" id="u6356b4c0">高扩展性</span></strong><span data-lake-id="u9b264632" id="u9b264632">：当节点数发生变化时，对于已经存在的数据，只有部分数据需要重新分布，不会影响到整体的数据结构。</span></li>
  </ol>
  <p data-lake-id="u5105dedd" id="u5105dedd"><span data-lake-id="u7af8d84e" id="u7af8d84e">​</span><br></p>
  <p data-lake-id="ucd19f5cd" id="ucd19f5cd"><span data-lake-id="uc4c641a7" id="uc4c641a7">但是，他也不是没有缺点的：</span></p>
  <p data-lake-id="u482b471c" id="u482b471c"><span data-lake-id="uf5efdd5e" id="uf5efdd5e">​</span><br></p>
  <ol list="ue5eec73f">
   <li fid="u25101824" data-lake-id="u75fa8da1" id="u75fa8da1"><strong><span data-lake-id="ucbc7d84d" id="ucbc7d84d">hash倾斜</span></strong><span data-lake-id="u66b146fa" id="u66b146fa">：在节点数较少的情况下，由于哈希空间是有限的，节点的分布可能不够均匀，导致数据倾斜。</span></li>
   <li fid="u25101824" data-lake-id="u1dcfe76a" id="u1dcfe76a"><strong><span data-lake-id="u3e06a062" id="u3e06a062">节点的频繁变更</span></strong><span data-lake-id="ub2d87754" id="ub2d87754">：如果频繁添加或删除节点，可能导致大量的数据迁移，造成系统压力。</span></li>
  </ol>
  <p data-lake-id="ub93d25e9" id="ub93d25e9"><br></p>
  <h1 data-lake-id="CHxBd" id="CHxBd"><span data-lake-id="u574a2306" id="u574a2306">扩展知识</span></h1>
  <h2 data-lake-id="MAC65" id="MAC65"><span data-lake-id="ued0055ec" id="ued0055ec">hash倾斜</span></h2>
  <p data-lake-id="ua66bb472" id="ua66bb472"><br></p>
  <p data-lake-id="uabb0ae06" id="uabb0ae06"><span data-lake-id="u9596c7ff" id="u9596c7ff">其实，hash倾斜带来的主要问题就是如果数据过于集中的话，就会使得节点数量发生变化时，数据的迁移成本过高。</span></p>
  <p data-lake-id="u8055b42d" id="u8055b42d"><span data-lake-id="u5c2be560" id="u5c2be560">​</span><br></p>
  <p data-lake-id="ubabac7b2" id="ubabac7b2"><span data-lake-id="ufec0f9b3" id="ufec0f9b3">那么想要解决这个问题，比较好的办法就是增加服务器节点，这样节点就会尽可能的分散了。</span></p>
  <p data-lake-id="u37296894" id="u37296894"><span data-lake-id="u72abe9b3" id="u72abe9b3">​</span><br></p>
  <p data-lake-id="u6bc5446a" id="u6bc5446a"><span data-lake-id="u2f54da6d" id="u2f54da6d">但是如果没有那么多服务器，我们也可以引入一些虚拟节点，把一个服务器节点，拆分成多个虚拟节点，然后数据在映射的时候先映射到虚拟节点，然后虚拟节点在找到对应的物理节点进行存储和读取就行了。</span></p>
  <p data-lake-id="u5dc49355" id="u5dc49355"><span data-lake-id="u34f718ec" id="u34f718ec">​</span><br></p>
  <p data-lake-id="uc3bcde70" id="uc3bcde70"><span data-lake-id="uf3a11e4b" id="uf3a11e4b">这时候，因为有虚拟节点的引入，数据就会比较分散，在增加或者减少服务器数量的时候，影响的数据就不会有那么多了。</span></p>
  <p data-lake-id="u261b31cc" id="u261b31cc"><br></p>
  <p data-lake-id="u84851f10" id="u84851f10"><br></p>
  <p data-lake-id="u6fe40514" id="u6fe40514"><br></p>
 </body>
</html>